package dfs

// https://leetcode-cn.com/problems/course-schedule-ii/
// 基本算法: 深度优先遍历
// 依次遍历每一个数字，然后遇到了需要遍历的数字就继续按这个数字来遍历，直到所有的数字都遍历完成
// 时间复杂度: O(n^2)
func FindOrder(numCourses int, prerequisites [][]int) []int {
	relyArr := make([][]int, numCourses)
	for _, currentRely := range prerequisites {
		if len(currentRely) != 2 || currentRely[0] >= numCourses || currentRely[1] >= numCourses {
			continue
		}
		if nil == relyArr[currentRely[0]] {
			relyArr[currentRely[0]] = make([]int, 0)
		}
		relyArr[currentRely[0]] = append(relyArr[currentRely[0]], currentRely[1])
	}

	courseArr := make([]int, 0, numCourses)
	hasLearnMap := make([]bool, numCourses)
	hasMarkMap := make([]bool, numCourses)
	for index := 0; index < numCourses; index++ {
		if !hasLearnMap[index] {
			var ok bool
			if courseArr, ok = recurForCourse(courseArr, index, relyArr, hasLearnMap, hasMarkMap); !ok {
				break
			}
		}
		if len(courseArr) == numCourses {
			break
		}
	}
	if len(courseArr) == numCourses {
		return courseArr
	} else {
		return []int{}
	}
}

// 真正的查找学习路径的递归方法
func recurForCourse(currentCourseArr []int, toLearnCourse int, relyArr [][]int, hasLearnMap []bool,
	hasMarkMap []bool) ([]int, bool) {
	// 循环依赖，直接退出
	if hasMarkMap[toLearnCourse] {
		return currentCourseArr, false
	}
	// 之前已经学习过的，不需要再学
	if hasLearnMap[toLearnCourse] {
		return currentCourseArr, true
	}
	// 有依赖关系的课程: 先把依赖的所有课程都学完，深度优先遍历
	if relyArr[toLearnCourse] != nil {
		hasMarkMap[toLearnCourse] = true
		for _, currentRelyCourse := range relyArr[toLearnCourse] {
			var ok bool
			if currentCourseArr, ok = recurForCourse(currentCourseArr, currentRelyCourse, relyArr, hasLearnMap,
				hasMarkMap); !ok {
				return currentCourseArr, false
			}
		}
		hasMarkMap[toLearnCourse] = false
	}
	currentCourseArr = append(currentCourseArr, toLearnCourse)
	hasLearnMap[toLearnCourse] = true
	return currentCourseArr, true
}
